/*
 *  Librarie de tipuri de date abstracte (TDA)
 
    Copyright (C) 2007  Catedra de Structuri de Date

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
 
#include <stdlib.h>
#include "linkedlist.h"

/*
 * Structures definitions
 */

struct linkedlist_node {
	void *data;
	struct linkedlist_node *next;
	struct linkedlist_node *prev;
};

struct linkedlist_adt {
	struct linkedlist_node *first;
	struct linkedlist_node *last;
	
	int count;
};

/*
 * Private functions
 */
 
 int _LL_ContainsIt(LinkedList list, LinkedListIterator it) {
 	LinkedListIterator crIt = list->first;
 	
 	if (it == NULL)
 		return 1;
 	
 	while (crIt != NULL) {
 		if (it == crIt)
 			return 1;
 			
 		crIt = crIt->next;
 	}
 	
 	return 0;
 }

/*
 * Public functions
 */

LinkedList LL_New() {
	LinkedList result;
	
	result = (LinkedList)malloc(sizeof(struct linkedlist_adt));
	
	// SUGESTIE: Nodul sentinela sa fie chiar NULL
	result->count = 0;
	result->first = NULL;
	result->last = NULL;
	
	return result;
}


void LL_Free(LinkedList list) {
	struct linkedlist_node *crNode, *prevNode;
	
	if(list == NULL)
		return;
	
	crNode = list->first;
	
	while (crNode != NULL) {
		prevNode = crNode;
		crNode = crNode->next;
		
		free(prevNode);
	}
	
	free(list);
}


int LL_Size(LinkedList list) {
	if( list == NULL )
		return -1;
		
	return list->count;
}

int LL_Empty(LinkedList list) {
	return (list->count == 0) ? 1 : 0;
}

LinkedListIterator LL_Begin(LinkedList list) {
	return list->first;
}

LinkedListIterator LL_End(LinkedList list) {
	return NULL;
}

LinkedListIterator LL_RBegin(LinkedList list) {
	return NULL;
}

LinkedListIterator LL_REnd(LinkedList list) {
	return list->last;
}

LinkedListIterator LL_Next(LinkedList list, LinkedListIterator it) {
	if (!_LL_ContainsIt(list, it))
		return NULL;
	
	if (it)
		return it->next;
	else
		return NULL;
}

LinkedListIterator LL_Prev(LinkedList list, LinkedListIterator it) {
	if (!_LL_ContainsIt(list, it))
		return NULL;
	
	if (it)
		return it->prev;
	else
		return NULL;
}

void LL_Add(LinkedList list, LinkedListIterator it, void *el) {
	LinkedListIterator newItem;
	if (list == NULL)
		return;
	
	if (!_LL_ContainsIt(list, it))
		return;
	
	newItem = (LinkedListIterator)malloc(sizeof(struct linkedlist_node));
	newItem->data = el;
	
	if (it) {
		newItem->next = it;
		
		if (it->prev) {
			newItem->prev = it->prev;
			it->prev->next = newItem;
		} else {
			newItem->prev = NULL;
			list->first = newItem;
		}
		
		it->prev = newItem;
	} else {
		newItem->next = NULL;
		newItem->prev = list->last;
		
		if (list->last) {
			list->last->next = newItem;
			list->last = newItem;
		} else {
			list->last = list->first = newItem;
		}
	}
	
	list->count++;
}

void *LL_Remove(LinkedList list, LinkedListIterator it) {		/* sugestion: shouldn't we use assert instead of returning NULL? */
	void *result = NULL;
	
	if(list == NULL)
		return NULL;
	
	if (!_LL_ContainsIt(list, it))
		return NULL;
		
	if (it == NULL)
		return NULL;
		
	result = it->data;
		
	if (it->prev) {
		it->prev->next = it->next;
	} else {
		list->first = it->next;
	}
	
	if (it->next) {
		it->next->prev = it->prev;
	} else {
		list->last = it->prev;
	}
	
	list->count--;
	free(it);
	
	return result;
}


void *LL_Get(LinkedList list, LinkedListIterator it) {
	if(list == NULL)
		return NULL;
	
	if (!_LL_ContainsIt(list, it)) {
		return NULL;
	}
	
	if (it == NULL) {
		return NULL;
	}
	
	return it->data;
}

void LL_Update(LinkedList list, LinkedListIterator it, void *el) {
/*
TODO: N-ar trebui eliberata memoria inainte? In cazul unor update repetate pe
acelasi element se pot produce memory-leaks. :-\
*/
	if (!_LL_ContainsIt(list, it))
		return;
		
	if (it == NULL)
		return;
		
	it->data = el;
}

LinkedListIterator LL_Find(LinkedList list, void *el) {
	LinkedListIterator crIt = list->first;	
	
	while (crIt != NULL) {
		if (crIt->data == el)
			return crIt;
			
		crIt = crIt->next;
	}
	
	return NULL;
}
